Corelab Seminar
2011-2012
Xaris Angelidakis (NTUA)
Some Techniques in Hardness of Approximation
Abstract.
In this talk, we will present some techniques about getting inapproximability results.
Such a result is a statement that a specific NP-hard problem is NP-hard to approximate within a certain factor.
We will show the connection between inapproximability and multi-prover interactive
proofs, which first appeared in a seminal paper in 1991 by Feige, Goldwasser, Lovasz,
Safra, and Szegedy, where they showed that results on interactive proofs could be used
to indicate the hardness of approximation of the MAX-CLIQUE in a graph.
We will then make a brief introduction to the PCP theorem, and we will conclude our talk by giving
some optimal PCP constructions due to Hastad that yield tight inapproximability results for
MAX-Ek-SAT and MAX-Ek-LIN-p (for both, k \geq 3), and improved inapproximability results for
MAX-E2-SAT, MAX-CUT and MAX-DI-CUT.